package __1背包

import "math"

/*
原题链接:
https://leetcode.cn/problems/target-sum/

代码随想录 动态规划章节
494. 目标和
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

目标和
给你一个非负整数数组 nums和一个整数target
向数组中的每个整数前添加+或

示例 1：
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：
输入：nums = [1], target = 1
输出：1

思路: 动态规划
在每一个元素前面放加法还是放减法, 就是把这个集合分成两个集合, 放加法的是一个集合, 放减法的是另外一个集合,
那么此题和 [分割等和子集] 和 [最后一块石头] 就很类似了

加法数字的集合, 声明为left
减法数字的集合, 声明为right

由上面逻辑可推得:
	left + right = sum				sum就是集合元素总和
	left - right = target			target就是目标值
上下两公式相加可得:
	2left = sum + target

所以, 此题就看能不能找到正数集合left = (target+sum) / 2
示例1中, nums[1,1,1,1,1]  target=3
	代入公式:　4 = (3 + 5) / 2
	所以示例1中, 只要能凑出这个使其和等于元素4, 有多少种这样的组合, 就作为结果输出
因为是找元素凑成4, 剩下元素的便都是负数了

如果出现 (target+sum) / 2不能整除的情况,
		(2 + 5) / 2,  7/2是不能整除的, 就意味着没有组合方案能凑成target, 直接return 0即可

总结: 该题最终转换为, 装满容量为left的容器, 有多少种方法 (前提是left是整除得到的)

一. dp[j]含义:
		装满容量为j的背包, 有dp[j]种方法

二. 递推公式
	例如: dp[4] 凑成 dp[5]
		 dp[3] 凑成 dp[5]
		 dp[2] 凑成 dp[5]
		 dp[1] 凑成 dp[5]
		 dp[0] 凑成 dp[5]

	dp[j] += dp[j-nums[j]]

二. 递推公式
	例如: dp[4] 能凑成 dp[5]
		 dp[3] 能凑成 dp[5]
		 dp[2] 能凑成 dp[5]  的可能数
		 dp[1] 能凑成 dp[5]  的可能数
		 dp[0] 能凑成 dp[5]  的可能数

	dp[j] = dp[j] + dp[j-nums[j]]


三. 初始化
	dp[0] = 1	装满容量为0的背包, 有1种方法
	非零下标初始为0即可, dp[j] += dp[j-nums[j]], 如果初始化为非零, 会影响递推公式推导

四. 遍历顺序
	先遍历物品, 后遍历背包   由于每个物品只能使用一次, 背包同样需要倒序遍历
	for (i=0; i<nums.size; i++)
		for(j=bagSize; j>=nums[i]; j--)
*/

func findTargetSumWays(nums []int, target int) int {
	sum := 0                 //1.声明总和
	for _, v := range nums { //遍历数组, 求总和
		sum += v
	}
	if abs(target) > sum { //条件判断1
		return 0
	}
	if (sum+target)%2 == 1 { //条件判断2
		return 0
	}

	bag := (sum + target) / 2 // 计算背包大小
	dp := make([]int, bag+1)  // 定义dp数组
	dp[0] = 1                 // 初始化

	for i := 0; i < len(nums); i++ { // 遍历顺序
		for j := bag; j >= nums[i]; j-- {
			dp[j] += dp[j-nums[i]] //推导公式
		}
	}
	return dp[bag]
}

func abs(x int) int {
	return int(math.Abs(float64(x)))
}
